ネットワーク分析:OpenFlightsデータセットの分析

image.png

OpenFlights.org (https://www.openflights.org/data.html) が提供している航空網のデータセットを対象としたネットワーク分析を行う。 航空網ネットワークの性質を調べたり、航空網のつながり方を用いた空港の分類重要な空港の発見を行う。

下準備

OpenFlightsのサイトにアクセスし、

をダウンロードする。

Q1. airports-extended.dat, routes.datの中身を確認する。

中身のテキストを確認できたらOK!

データ読み込み

Q2. airports-extended.dat, routes.dat をpandasのdataframeとして読み込む。

さらに、https://www.openflights.org/data.html を参考に、各列に適切な名前をつける。

(ヒント)

ネットワークを作る

Q3. 各空港をノード、空港間を結ぶ路線をエッジとしたネットワークを作成する。

(ヒント)

ネットワークを描画する

Q4. 各空港データに存在する緯度・経度のデータを用いて、航空網ネットワークを描画する。

(ヒント)

エラーがでる。おそらく原因は、各空港データ (airports-extended.dat)にすべての空港の緯度・経度が含まれていないせい。 仕方がないので、今回の描画はそこに含まれる空港のみを抽出して行う。

ちなみに、ネットワーク構造の可視化は GephiCytoscape といったソフトウェアを用いて行うのもよい

ネットワークの性質を調べる

Q5. 航空網ネットワークの次数分布を描画する。

縦軸・横軸は対数軸でプロットする。

(ヒント)

https://ja.wikipedia.org/wiki/%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF#%E3%82%B9%E3%82%B1%E3%83%BC%E3%83%AB%E3%83%95%E3%83%AA%E3%83%BC%E6%80%A7

Q6. ネットワークの接続成分(connected components)、最大接続成分(largest connected component)を抽出する

あるネットワークのうち、任意のノード間にパス(経路)が存在するサブグラフを接続成分(connected components)という。特に、ネットワーク内で最大の接続成分を最大接続成分(largest connected component)という。

(例)以下のネットワークには、接続成分が3つある。 image.png

connected_componentsのドキュメントを読むと、Returnsの部分に

A generator of sets of nodes, one for each component of G.

と書いてある。

ここから、connected_componentsの返り値は「各接続成分のノードセットのgenerator」であることがわかる。

generator型オブジェクトはfor文で中身を取り出すことができるほか、list()を適用することでlist型に変換することができる。

一つ目のconnected componentsが最大であるため、それを抽出する。

Q7. 最大接続成分の直径・平均パス長を求める

ネットワークから最大接続成分を抽出することで、平均パス長(ネットワークに含まれるノードの全ペアの最短経路長を平均した値)や、直径(ネットワーク内の最大の最短経路長)といった値を求められるようになる。これらは、ネットワークの性質を示す重要な値である。

今回の航空網ネットワークではほとんどのノードが最大接続成分に含まれるため、最大接続成分の性質を調べることでもネットワーク全体の性質を知ることができた、といえるだろう。

Q8. 最大接続成分の直径・平均パス長をErdős–Rényi modelのランダムグラフと比較する

あるネットワーク固有の性質を調べるためのアプローチとして、null model(帰無仮説ネットワーク)と比較する方法がある。

「現実のネットワーク」と、「null model (= あるランダムなネットワーク生成アルゴリズムによって、ノード数や次数などの基本的な性質が同じになるように再現したネットワーク)」を比較する。このとき、ネットワーク特徴の指標(直径、平均パス長、ネットワーク・モチーフ、etc...)に有意な差がみられる場合、その部分に現実のネットワークの構造を規定する制約が反映されているのではないか?と考えられる。ひいては、現実世界のシステムを理解する手がかりになる。

(ヒント)

ノード数・エッジ数を再現したランダムグラフよりも、実際の航空網ネットワークのほうが直径・平均パス長ともに大きい。このような差を生み出す原因には、ランダムグラフで考慮されていなかった地理的要因や政治的要因などがあると考えられる。

ランダムグラフの生成アルゴリズムにそのような要因を追加して、再び現実の航空網と比較し、指標をよりよく再現できているか?を確かめることで、現実の航空網ネットワークを生み出すメカニズムをよりよく理解できる。

(注:本当はランダムグラフを複数サンプリングしたり、ランダム化した場合の値を解析的に求めたりして、より厳密にやる必要があるかもしれない。)

ネットワークの中心性分析を行う

Q9. 各空港ノードの次数中心性・媒介中心性を求める

次数中心性

媒介中心性

次数中心性とは異なる結果が得られた。

例えばアラスカの真ん中あたりにある空港は、次数中心性の図では小さかったものの媒介中心性の図では大きい。この空港は規模こそ大きくないものの、航空網のつながりという観点では重要な空港である、といえるかもしれない。

他の中心性

ここにたくさん載っている

ネットワークのコミュニティ検出(クラスタリング)を行う

Q10. 貪欲法を用いたmodularityの最大化によってコミュニティを検出する

(%%time をセルの一番上に書くと、実行時間を計測できる。)

Q11. どのようにクラスタリングされているか知るために、各クラスタに色をつけて描画する

Q12. Functional Cartographyを用いて、各ノードの役割を分類する

Functional Cartographyの説明

https://sites.google.com/site/kztakemoto/r-seminar-on-igraph---supplementary-information#cartography より引用。

大規模なネットワークにおいてノードの役割や性質が分類できると便利ですよね。ひとつの考え方としてFunctional Cartography(Guimera & Amaral, 2005)という分類法があります。これはコミュニティ検出アルゴリズムなどをもちいてネットワークをモジュール分割し、モジュール内・外に対してノードがどのような役割を果たしているのかを特徴付けます。具体的には以下のように分類されます。 - R1: Ultra-peripheral nodes. 「超」周辺ノード - R2: Peripheral nodes. 周辺ノード - R3: Non-hub connectors. ハブではないが、複数のモジュールをつなぐコネクター - R4: Non-hub kinless nodes. ハブではないが、多くのモジュールにつながるノード - R5: Provincial hubs. モジュール内のハブ - R6: Connector hubs. 複数のモジュールをつなぐハブ - R7: Kinless hubs. 多くのモジュールにつながるハブ 例えば、ハブの存在するネットワークではハブの攻撃に対して脆弱(Albert et al., 2000)ですが、モジュール内のハブを攻撃するのと複数のモジュールをつなぐハブを攻撃するのとでは挙動が違います(Han et al., 2004)。このように、この分類で重要そうなノードを絞り込むことができます。

具体的な手法

Functional Cartographyでは、コミュニティ検出によりモジュールに分けられた各ノードに対して、次の2つの値を求める。

Within-module degree : z
$$ z_i = \frac{k_i - \overline{k_{s_i}}}{\sigma_{s_i}} $$

ただし、

Participation coefficient : P
$$ P_i = 1 - \sum^{N_m}_{s=1}{(\frac{k_{is}}{k_i})^2} $$

ただし、

これら2つの値を用いて、全ノードを以下のようにポジショニングし、分類する。

スクリーンショット 2021-11-06 11.55.27.png

Functional Cartographyが提案された論文 : Functional cartography of complex metabolic networks

わかりやすくするため描画する

Q13. (おまけ)Infomap法でコミュニティ検出を行う

Infomap法のpythonパッケージが公開されている( https://pypi.org/project/infomap/ )が、Windowsではパッケージをインストールできない。公式サイトにも

A pre-compiled version is available for macOS users.

と載っている。

そこで、今回はGoogle Colaboratoryを用いた方法を紹介する。 Google ColaboratoryではinfomapのPythonパッケージを使用することができる。

Google Colaboratoryの紹介 : https://gammasoft.jp/blog/google-colaboratory-for-learning/

  1. まず、ネットワークのデータをGoogle Colaboratoryにコピーするため、ファイル (routes.net) に出力する。

続きはGoogle Colaboratoryでおこなう

https://colab.research.google.com/drive/1O1bPux0vjLyp7wvuDM4p86zhiLTnntCi?usp=sharing にコードがある


Google ColaboratoryでInfomapによるコミュニティ検出を行い、実行結果の modules.pickle ファイルが生成できたら、ダウンロードしてこのnotebookで読み込めるようにする。

Modularity最大化とは違う分け方のコミュニティが得られた。